package com.fps.webshop.question.question0001_0099;

/**
 * 5. 最长回文子串
 * 
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 
 * 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
 * 
 * 示例 2： 输入：s = "cbbd" 输出："bb"
 * 
 * 示例 3： 输入：s = "a" 输出："a"
 * 
 * 示例 4： 输入：s = "ac" 输出："a"
 * 
 * 提示： 1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成
 */
public class Question005 {

	/**
	 * 第一次提交，使用了指针不断像两边试探的方式，但结果很不理想，时间极大
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		489 ms	39 MB	Java	2021/08/05 09:51
	 */
	public static String longestPalindrome(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;

			for (int i = 0; i < s.length(); i++) {
				if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
					theWord = s.charAt(nowpoint)+"";
				}
				if (startPoint < 0)
					continue;
				if (endPoint >= s.length()) {
					continue;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
				endPoint++;
			}
			
		}
		// 计算双回文
		nowpoint = 0;
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			for (int i = 0; i < s.length(); i++) {
				endPoint++;
				if (startPoint < 0)
					continue;
				if (endPoint >= s.length()) {
					continue;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
			}
		}
		return theWord;

	}
	
	/**
	 * 第二次提交，将几个continue改为break，时间有所提升，但结果依旧不是很理想
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		281 ms	39.2 MB	Java	2021/08/05 09:53
	 */
	public static String longestPalindrome2(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;

			for (int i = 0; i < s.length(); i++) {
				if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
					theWord = s.charAt(nowpoint)+"";
				}
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					break;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
				endPoint++;
			}
			
		}
		// 计算双回文
		nowpoint = 0;
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			for (int i = 0; i < s.length(); i++) {
				endPoint++;
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					break;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
			}
		}
		return theWord;

	}

	
	/**
	 * 第三次提交，将两个for循环合并成一个，但时间反而增加了？？！！为什么，消耗在了哪里？
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		347 ms	39.9 MB	Java	2021/08/05 10:31
	 */
	public static String longestPalindrome3(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			int endPoint2 = nowpoint;
			
			Boolean isEnd1 = false;
			Boolean isEnd2 = false;
			
			for (int i = 0; i < s.length(); i++) {
				if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
					theWord = s.charAt(nowpoint)+"";
				}
				endPoint2++;
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					isEnd1 = true;
				}
				if (endPoint2 >= s.length()) {
					isEnd2 = true;
				}
				
				if(isEnd1&&isEnd2) {
					break;
				}else if(isEnd1&&!isEnd2) {
					if (s.charAt(startPoint) == s.charAt(endPoint2)) {
						if (s.substring(startPoint, endPoint2+1).length() > theWord.length()) {
							theWord = s.substring(startPoint, endPoint2+1);
						}
					} else {
						if (s.substring(startPoint+1, endPoint2).length() > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint2);
						}
						isEnd2 = true;
					}
				}else if(!isEnd1&&isEnd2) {
					if (s.charAt(startPoint) == s.charAt(endPoint)) {
						if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
							theWord = s.substring(startPoint, endPoint+1);
						}
					} else {
						if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint);
						}
						isEnd1 = true;
					}
				}else {
					if (s.charAt(startPoint) == s.charAt(endPoint)||s.charAt(startPoint) == s.charAt(endPoint2)) {
						if(s.charAt(startPoint) == s.charAt(endPoint)) {
							if (s.substring(startPoint, endPoint+1).length() > theWord.length()) {
								theWord = s.substring(startPoint, endPoint+1);
							}
						}else {
							isEnd1 = true;
						}
						if(s.charAt(startPoint) == s.charAt(endPoint2)) {
							if (s.substring(startPoint, endPoint2+1).length() > theWord.length()) {
								theWord = s.substring(startPoint, endPoint2+1);
							}
						}else {
							isEnd2 = true;
						}
						
					} else {
						if (s.substring(startPoint+1, endPoint).length() > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint);
						}
						if (s.substring(startPoint+1, endPoint2).length() > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint2);
						}
                        isEnd1 = true;
						isEnd2 = true;
					}
				}
				
				startPoint--;
				endPoint++;
			}
		}
		return theWord;
	}
	
	/**
	 * 第四次提交，在第三次的基础上，去掉截取String再判断长度的操作
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		114 ms	39.7 MB	Java	2021/08/05 10:58
	 */
	public static String longestPalindrome4(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			int endPoint2 = nowpoint;
			
			Boolean isEnd1 = false;
			Boolean isEnd2 = false;
			
			for (int i = 0; i < s.length(); i++) {
				if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
					theWord = s.charAt(nowpoint)+"";
				}
				endPoint2++;
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					isEnd1 = true;
				}
				if (endPoint2 >= s.length()) {
					isEnd2 = true;
				}
				
				if(isEnd1&&isEnd2) {
					break;
				}else if(isEnd1&&!isEnd2) {
					if (s.charAt(startPoint) == s.charAt(endPoint2)) {
						if ((endPoint2+1-startPoint) > theWord.length()) {
							theWord = s.substring(startPoint, endPoint2+1);
						}
					} else {
						if ((endPoint2-startPoint-1) > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint2);
						}
						isEnd2 = true;
					}
				}else if(!isEnd1&&isEnd2) {
					if (s.charAt(startPoint) == s.charAt(endPoint)) {
						if ((endPoint+1-startPoint) > theWord.length()) {
							theWord = s.substring(startPoint, endPoint+1);
						}
					} else {
						if ((endPoint-startPoint-1) > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint);
						}
						isEnd1 = true;
					}
				}else {
					if (s.charAt(startPoint) == s.charAt(endPoint)||s.charAt(startPoint) == s.charAt(endPoint2)) {
						if(s.charAt(startPoint) == s.charAt(endPoint)) {
							if ((endPoint+1-startPoint) > theWord.length()) {
								theWord = s.substring(startPoint, endPoint+1);
							}
						}else {
							isEnd1 = true;
						}
						if(s.charAt(startPoint) == s.charAt(endPoint2)) {
							if ((endPoint2+1-startPoint) > theWord.length()) {
								theWord = s.substring(startPoint, endPoint2+1);
							}
						}else {
							isEnd2 = true;
						}
						
					} else {
						if ((endPoint-startPoint-1) > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint);
						}
						if ((endPoint2-startPoint-1) > theWord.length()) {
							theWord = s.substring(startPoint+1, endPoint2);
						}
						isEnd1 = true;
						isEnd2 = true;
					}
				}
				
				startPoint--;
				endPoint++;
			}
		}
		return theWord;
	}
	
	
	/**
	 * 第五次提交，在第二次提交的基础上，去掉截取String再判断长度的操作
	 * 确实快了，但还是不明白为什么两次循环反而要比一次循环慢，是判断太多了吗？
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		100 ms	39 MB	Java	2021/08/05 11:01
	 */
	public static String longestPalindrome5(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;

			for (int i = 0; i < s.length(); i++) {
				if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
					theWord = s.charAt(nowpoint)+"";
				}
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					break;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if ((endPoint+1-startPoint) > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if ((endPoint-startPoint-1) > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
				endPoint++;
			}
			
		}
		// 计算双回文
		nowpoint = 0;
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			for (int i = 0; i < s.length(); i++) {
				endPoint++;
				if (startPoint < 0)
					break;
				if (endPoint >= s.length()) {
					break;
				}
				if (s.charAt(startPoint) == s.charAt(endPoint)) {
					if ((endPoint+1-startPoint) > theWord.length()) {
						theWord = s.substring(startPoint, endPoint+1);
					}
				} else {
					if ((endPoint-startPoint-1) > theWord.length()) {
						theWord = s.substring(startPoint+1, endPoint);
					}
					break;
				}
				startPoint--;
			}
		}
		return theWord;

	}
	
	
	/**
	 * 第六次提交，在第四次的基础上，尝试修改
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		48 ms	39.1 MB	Java	2021/08/05 14:02
	 */
	public static String longestPalindrome6(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			
			if ((s.charAt(nowpoint)+"").length() > theWord.length()) {
				theWord = s.charAt(nowpoint)+"";
			}
			
			//两个独立的循环
			while((endPoint+1)<s.length()&&s.charAt(startPoint)==s.charAt(endPoint+1)) {
				endPoint++;
				if ((endPoint+1-startPoint) > theWord.length()) {
					theWord = s.substring(startPoint, endPoint+1);
				}
			}
			while((startPoint-1)>=0&&(endPoint+1)<s.length()&&s.charAt(startPoint-1)==s.charAt(endPoint+1)) {
				startPoint--;
				endPoint++;
				if ((endPoint+1-startPoint) > theWord.length()) {
					theWord = s.substring(startPoint, endPoint+1);
				}
			}
		}
		return theWord;
	}
	
	/**
	 * 第七次提交，记录theWord的长度，而不是直接累次通过.length()获取长度
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		37 ms	38.8 MB	Java	2021/08/05 14:06
	 */
	public static String longestPalindrome7(String s) {
		// 记录当前点
		int nowpoint = 0;
		String theWord = "";
		int length=0;
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			
			if ((s.charAt(nowpoint)+"").length() > length) {
				theWord = s.charAt(nowpoint)+"";
				length = 1;
			}
			
			//两个独立的循环
			while((endPoint+1)<s.length()&&s.charAt(startPoint)==s.charAt(endPoint+1)) {
				endPoint++;
				if ((endPoint+1-startPoint) > length) {
					theWord = s.substring(startPoint, endPoint+1);
					length = endPoint+1-startPoint;
				}
			}
			while((startPoint-1)>=0&&(endPoint+1)<s.length()&&s.charAt(startPoint-1)==s.charAt(endPoint+1)) {
				startPoint--;
				endPoint++;
				if ((endPoint+1-startPoint) > length) {
					theWord = s.substring(startPoint, endPoint+1);
					length = endPoint+1-startPoint;
				}
			}
		}
		return theWord;
	}
	
	
	/**
	 * 第八次提交，不每次获取theWord，而是改用两个字段记录位置，最后计算。
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		32 ms	38.4 MB	Java	2021/08/05 14:15
	 */
	public static String longestPalindrome8(String s) {
		// 记录当前点
		int nowpoint = 0;
		int length=0;
		int a=0;
		int b=0;
		
		// 计算单回文
		for (; nowpoint < s.length(); nowpoint++) {
			int startPoint = nowpoint;
			int endPoint = nowpoint;
			
			if (1 > length) {
				a = nowpoint;
				b = nowpoint+1;
				length = 1;
			}
			
			//两个独立的循环
			while((endPoint+1)<s.length()&&s.charAt(startPoint)==s.charAt(endPoint+1)) {
				endPoint++;
				if ((endPoint+1-startPoint) > length) {
					a=startPoint;
					b=endPoint+1;
					length = endPoint+1-startPoint;
				}
			}
			while((startPoint-1)>=0&&(endPoint+1)<s.length()&&s.charAt(startPoint-1)==s.charAt(endPoint+1)) {
				startPoint--;
				endPoint++;
				if ((endPoint+1-startPoint) > length) {
					a=startPoint;
					b=endPoint+1;
					length = endPoint+1-startPoint;
				}
			}
		}
		return s.substring(a, b);
	}
	
	public static void main(String[] args) {
		String s = "aaaa";
		System.out.print(longestPalindrome6(s));
	}

}
